<!DOCTYPE html>
<html>

<head>
    <meta charset="utf-8">
    <title>Maxmilite</title>
    <link rel="icon" href="../icon.png" type="image/x-icon">
</head>

<link rel="stylesheet" href="../css/style-archive.css">

<canvas id="snow-flake-app"></canvas>
<script src="../js/snow-flake-app.js"></script>

<!-- <ul class="nav">
    <li style="width: 40%;">
        <div>
            <p style="font-size: xx-large;"><img src="../icon.png" height="40px" width="40px"
                    style="border-radius: 4px;">&nbsp;Maxmilite</p>
        </div>
    </li>
</ul> -->

<div class="main">
    <h1 style="text-align: center;">
        题解 P7107 【天选之人】
    </h1>
</div>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});
</script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<xmp theme="united" style="display:none;" id="section">
## Solution

按照题面要求，在 $m$ 个人中恰好有 $p$ 个人抽到的带记号纸团数相同且最多。

所以我们不妨小小贪心一下**直接让他们往多里拿，能拿多少拿多少**

#### 正确性证明

~~其实非常简单，你拿的多了那么剩下的人拿的就少了，你自然拿到的就更多~~

我们不妨先假设他们每个人都拿了 $damedane$ 个带记号的纸团罢

` int damedane; `

那么 $damedane$ 需要满足什么条件呢？

1. 你不能从四维空间里拿出带记号纸团来，所以所有 $p$ 个人一共只能拿不大于 $k$ 个带记号纸团：$damedane \times p <= k$
2. 俗话讲不能吃不该吃的东西，所以每个人只能拿至多 $m$ 个纸团：$damedane <= m$

所以最大值要怎么取呢？

$damedane = min (k \div p , m)$

即 ` damedane = k / p > m ? m : k / p; `

既然这 $p$ 个人每个人都拿了最多的纸团了，那么我们就开始验证罢。

什么条件下这种情况就成立了呢？

1. 剩下的在尽可能多的情况下每个人都比这 $p$ 个人拿的少

对就一条。

那么怎么让剩下的每个人都比这 $p$ 个人拿的少的情况下都拿尽可能多呢？

我们不妨先假设他们每个人都拿了 $dameyo$ 个带记号的纸团罢

` int dameyo; `

怎么样最少？

每个剩下的都拿 $(damedame - 1)$ 个，直到拿完为止。

#### 正确性证明

~~其实更简单，你拿的少了同类兄弟要分摊的就多了，所以你要尽可能多拿~~

然后我们就可以算 $dameyo$ 了

对 $dameyo$ ，我们可以通过以下方式计算：

对前 $\frac{(k - damedane \times p)}{damedane - 1}$ 个，每个人拿 $damedane - 1$ 个

如果有多余的话，再来一个兜底

剩下的不拿

然后我们判断下所有 $n - p$ 个人拿完以后剩没剩下就可以了

怎么判断呢？

判断$\frac{(k - damedane \times p)}{damedane - 1}$ ( 可能 + 1 ) 个人有没有超过 $n - p$ 就可以了

### 特判1

_" 如果有多余的话，再来一个兜底 "_

其实这个多余的就是判断下 $\frac{(k - damedane \times p)}{damedane - 1}$ 有没有余数就可以了

_" 可能 + 1 "_

### 特判2

一种情况是 $n = p$ ，所以如果按照上面的式子来算 $dameyo$ 的话就会很悲惨的

**$Segmention \ Fault$**

(除数为0)

所以加个特判就好了

(这俩特判搞了我一个半小时)

## AC Code ( C Language )
```cpp
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
long long n, m, k, p, t, tot, tmp;
int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &k, &p);
    tot = k;
    t = k / p > m ? m : k / p;
    tot -= t * p;
    if (n == p)
    {
        if (t * p == k)
        {
            printf("YES\n");
            for (int i = 1; i <= n; ++i)
                printf("%lld %lld\n", t, m - t);
        }
        else
            printf("NO\n");
    }
    else
    {

        if ((n - p) * (t - 1) < tot)
            printf("NO\n");
        else
        {
            printf("YES\n");
            for (int i = 1; i <= p; ++i)
                printf("%lld %lld\n", t, m - t);
            for (int i = p + 1; i <= n; ++i)
            {
                if (tot < (t - 1))
                    printf("%lld %lld\n", tot, m - tot);
                else
                    printf("%lld %lld\n", t - 1, m - t + 1);
                tot -= t - 1;
                if (tot < 0)
                    tot = 0;
            }
        }
    }
    return 0;
}
```
</xmp>


<script src="strapdown/v/0.2/strapdown.js"></script>

<div>
    <!-- Button Here -->
    <!-- Fixed Button 2021-04-18-->
    <a class="button" href="../archives.html" style="width: 40%; border-radius: 8px; margin-left: 30%; margin-top: 100px;  margin-bottom: 40px">
        <p style="font-size: 2vmax;">
            <<< Return to archive list </p>
    </a>
</div>

</html>